package practice_2025_9.practice_9_21;

import practice_2025_9.practice_9_5.ListNode;

class Solution {
    /**
     * 旋转链表
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        // 计算要移动的节点数
        int len = 0;
        ListNode cur = head;
        // 记录最后一个节点
        ListNode last = null;
        while(cur != null) {
            len++;
            if (cur.next == null) {
                last = cur;
            }
            cur = cur.next;
        }
        // 计算左旋节点个数
        int count = len - k % len;
        // System.out.println(len + " count" + (k % len));
        if (count == 0) {
            return head;
        }
        // 将后续节点插入到 head 之前
        ListNode prev = null;
        cur = head;
        while(cur != null && count-- > 0) {
            prev = cur;
            cur = cur.next;
        }
        // 后续无节点，无需旋转
        if (cur == null) {
            return head;
        }
        prev.next = null;
        last.next = head;
        return cur;
    }

    /**
     * 旋转链表
     * 将尾节点与头节点相连, 找到要左旋的节点，断开，形成新的链表
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight2(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        int len = 1;
        ListNode cur = head;
        while(cur.next != null) {
            cur = cur.next;
            len++;
        }
        int begin = len - (k % len);
        if (begin == 0) {
            return head;
        }
        cur.next = head;
        cur = head;
        while(begin-- > 1) {
            cur = cur.next;
        }
        ListNode newHead = cur.next;
        cur.next = null;
        return newHead;
    }
}